package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 中档题
 * 147. 对链表进行插入排序
 * 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
 * <p>
 * 插入排序 算法的步骤:
 * <p>
 * 1、插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 2、每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 3、重复直到所有输入数据插入完为止。
 * <p>
 * 对链表进行插入排序。
 * <p>
 * 输入: head = [-1,5,3,4,0]
 * 输出: [-1,0,3,4,5]
 * <p>
 * 输入: head = [4,2,1,3]
 * 输出: [1,2,3,4]
 *
 * @author zjj_admin
 * @date 2022/11/17 9:37
 */
public class InsertionSortList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(3, null);
        ListNode node2 = new ListNode(0, node1);
        ListNode node3 = new ListNode(4, node2);
        ListNode node4 = new ListNode(1, node3);
        ListNode node5 = new ListNode(3, node4);
        ListNode node6 = new ListNode(1, node5);
        ListNode node7 = new ListNode(4, node6);
        ListNode node8 = new ListNode(0, node7);
        ListNode node9 = new ListNode(2, node8);

        insertionSortList2(node3);
        System.out.println("node3 = " + node3);

    }


    /**
     * 使用插入排序方式为链表排序
     * 时间
     * 25 ms
     * 击败
     * 10.81%
     * 内存
     * 40.9 MB
     * 击败
     * 69.67%
     *
     * @param head
     * @return
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //新链表的虚拟头结点
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        while (head != null) {
            ListNode pre = null, curr = dummy;
            while (curr != null) {
                if (curr.val > head.val) {
                    break;
                }
                pre = curr;
                curr = curr.next;
            }
            pre.next = new ListNode(head.val, curr);
            head = head.next;

        }
        return dummy.next;
    }


    public static ListNode insertionSortList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //新链表的虚拟头结点
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode tail = new ListNode();
        while (head != null) {
            ListNode pre = dummy, curr = dummy.next;
            while (curr != head) {
                if (curr.val > head.val) {
                    break;
                }
                pre = pre.next;
                curr = curr.next;
            }
            pre.next = new ListNode(head.val, curr);
            tail = dummy.next;
            while (tail != head){
                tail = tail.next;
            }
//            curr.next = curr.next.next;
            head = head.next;
            if(head.next == null){
                tail.next = null;
            }else {
                tail.next = tail.next.next;
            }


        }
        return dummy.next;
    }


}
